package cn.fxzhang.leetcode.no00;

import java.util.HashMap;
import java.util.Map;

/**
 * 1.两数之和
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[0,1]
 * 链接：https://leetcode-cn.com/problems/two-sum
 *
 * 类型：数组
 * 题解：通过哈希表，寻找 target - x 所在位置
 * 时间复杂度：O(N), N是数组中的元素数量
 * 空间复杂度：O(N), N是数组中的元素数量。主要为哈希表的开销
 *
 * 提交记录(1/1-通过次数/提交次数)：
 * 执行用时: 0 ms，击败了100.00%
 * 内存消耗: 38.6 MB，击败了52.00%
 *
 *【简单】通过次数1,910,641提交次数3,766,209
 * @author 张晓帆
 * @date 2021/3/29
 */
public class P0001_Two_Sum {

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(target - num)){
                return new int[]{map.get(target - num), i};
            }
            map.put(num, i);
        }
        return new int[]{};
    }

}
